/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BASB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=MATH30/FONT#8=FIX25/FONT#9=GRKB30
␈↓ α∧␈↓␈↓ u1


␈↓ α∧␈↓α␈↓ βdCS206   Recursive Programming and Proving          Fall 1980

␈↓ α∧␈↓α␈↓ ¬lMidterm Examination

␈↓ α∧␈↓α␈↓ ε5Nov 14 1980



␈↓ α∧␈↓Write the following programs using either Maclisp or external notation.

␈↓ α∧␈↓You may use any books or notes that you wish on this test.



␈↓ α∧␈↓1.a. ␈↓↓least[u]␈↓ is the least integer in the list ␈↓↓u␈↓ of integers.

␈↓ α∧␈↓b. ␈↓↓least1[x]␈↓ is the least integer in the s-expression ␈↓↓x␈↓, all of whose atoms are assumed to be integers.

␈↓ α∧␈↓2. a. ␈↓↓flip2 u␈↓ reverses each pair of successive elements of ␈↓↓u␈↓ starting with the first.  Thus

␈↓ α∧␈↓␈↓ αT␈↓↓flip2 ␈↓(A B C D) = (B A D C)

␈↓ α∧␈↓and

␈↓ α∧␈↓␈↓ αT␈↓↓flip2 ␈↓(A B C D E) = (B A D C E).

␈↓ α∧␈↓b. Prove that ␈↓↓∀u.[flip2 flip2 u = u]␈↓.

␈↓ α∧␈↓3. a. Defining

␈↓ α∧␈↓␈↓ αT␈↓↓nth[u,n] ← ␈↓αif␈↓↓ n equal 1 ␈↓αthen␈↓↓ ␈↓αa␈↓↓ u ␈↓αelse␈↓↓ nth[␈↓αd␈↓↓ u, n-1]␈↓

␈↓ α∧␈↓and

␈↓ α∧␈↓␈↓ αT␈↓↓index[u,x] ← ␈↓αif␈↓↓ x equal ␈↓αa␈↓↓ u ␈↓αthen␈↓↓ 1 ␈↓αelse␈↓↓ 1 + index[␈↓αd␈↓↓ u, x]␈↓,

␈↓ α∧␈↓prove

␈↓ α∧␈↓␈↓ αT␈↓↓∀x u.[member[x,u] ⊃ nth[u,index[u,x]] = x]␈↓.

␈↓ α∧␈↓b. What additional conditions are require to prove

␈↓ α∧␈↓␈↓ αT␈↓↓index[u, nth[u, k]] = k␈↓?

␈↓ α∧␈↓Don't give the proof.

␈↓ α∧␈↓4.␈αAssume␈α
that␈α␈↓↓u␈↓␈α
is␈αa␈α
list␈αof␈α
lists␈αof␈α
equal␈αlength␈α
representing␈αa␈α
matrix␈αlisted␈α
by␈αrows.␈α ␈↓↓transpose␈α
u␈↓
␈↓ α∧␈↓represents the transpose of the matrix.  Thus

␈↓ α∧␈↓␈↓ αT␈↓↓transpose ␈↓((A B C) (D E F)) = ((A D) (B E) (C F)).
␈↓ α∧␈↓␈↓ u2


␈↓ α∧␈↓5. The Linus sequence Linus(i) is an infinite sequence of 1's and 0's defined as follows:

␈↓ α∧␈↓␈↓ αTLinus(1) = 1

␈↓ α∧␈↓␈↓ αTLinus(i) = the number which breaks the longest "pattern" which is threatening to occur,

␈↓ α∧␈↓␈↓ αTwhere␈αa␈α"pattern"␈αis␈αdefined␈αto␈αbe␈αtwo␈αconsecutive␈αoccurrences␈αof␈αthe␈αsame␈αstring␈αof␈α1's␈αand
␈↓ α∧␈↓0's. The length of a pattern is defined to be the length of one of its halves. For instance,

␈↓ α∧␈↓␈↓ αT␈↓ αTLength␈↓ β4Pattern
␈↓ α∧␈↓␈↓ αT␈↓ αT1␈↓ β40 0
␈↓ α∧␈↓␈↓ αT␈↓ αT1␈↓ β41 1
␈↓ α∧␈↓␈↓ αT␈↓ αT2␈↓ β41 0 1 0
␈↓ α∧␈↓␈↓ αT␈↓ αT3␈↓ β41 0 1 1 0 1
␈↓ α∧␈↓␈↓ αT␈↓ αT4␈↓ β41 1 0 1 1 1 0 1


␈↓ α∧␈↓␈↓ αTThe first 12 terms of the Linus sequence are:

␈↓ α∧␈↓␈↓ αT1 0 1 1 0 0 1 0 1 1 0 1

␈↓ α∧␈↓␈↓ αTLinus(2)=0␈αsince␈αotherwise␈αwe␈αcreate␈αthe␈αlength␈α1␈α
pattern␈α"1␈α1".␈αClearly␈αthe␈αnext␈αterm␈αin␈α
the
␈↓ α∧␈↓Linus␈αsequence␈αis␈αalways␈αforced,␈αsince␈αwe␈αcan␈α
always␈αbreak␈αa␈αpattern␈αof␈αat␈αleast␈αlength␈α1.␈α
Linus(4)
␈↓ α∧␈↓avoids␈α
the␈α
pattern␈α
"1␈α
0␈α
1␈α
0".␈α
 Linus(12)␈α
creates␈α∞the␈α
pattern␈α
"1␈α
0␈α
1␈α
1␈α
0␈α
1",␈α
but␈α
avoids␈α∞the␈α
longer
␈↓ α∧␈↓pattern "1 0 1 1 0 0 1 0 1 1 0 0".

␈↓ α∧␈↓␈↓ αTProblem.␈αWrite␈α
the␈αfunction␈αLinus[u]␈α
which␈αappends␈α
the␈αnext␈αterm␈α
in␈αthe␈α
Linus␈αsequence
␈↓ α∧␈↓to the beginning of u, where u is a list of the form

␈↓ α∧␈↓␈↓ αT[Linus(n), Linus(n-1), Linus(n-2)... Linus(2), Linus(1)]